package C018;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * ClassName: PreOrder
 * Package: C018
 * Description:
 *
 * @Author BCXJ
 * @Create 2024/12/5 10:48
 * @Version 1.0
 * @Since 1.0
 */
public class MyTest {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int v) {
            val = v;
        }
    }


    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
        head.left.left = new TreeNode(4);
        head.left.right = new TreeNode(5);
        head.right.left = new TreeNode(6);
        head.right.right = new TreeNode(7);
        preOrder(head);
        System.out.println("先序遍历非递归版");
        inOrder(head);
        System.out.println("中序遍历非递归版");
        posOrderTwoStacks(head);
        System.out.println("后序遍历非递归版 - 2个栈实现");
        posOrderOneStack(head);
        System.out.println("后序遍历非递归版 - 1个栈实现");
    }

    /**
     * 非递归先序遍历
     *
     * @param root
     */
    public static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode node;
        while (!stack.isEmpty()) {
            node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        System.out.println();
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode node;
        while (!stack.isEmpty()) {
            node = stack.pop();
            list.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return list;
    }

    /**
     * 非递归中序遍历
     *
     * @param head
     */
    public static void inOrder(TreeNode head) {
        if (head == null) {
            return;
        }
        TreeNode cur = head;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            if(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }else {
                cur = stack.pop();
                System.out.print(cur.val + " ");
                cur = cur.right;
            }
        }
        System.out.println();
    }

    public static List<Integer> inOrder2(TreeNode head) {
        List<Integer> list = new ArrayList<>();
        if (head == null) {
            return list;
        }
        TreeNode cur = head;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            if(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }else {
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }


    /**
     * 后序遍历 - 双栈实现
     * 思考一下：后序 左右中, 先序的顺序是 中左右， 后面改为 中右左的形式压栈，然后再弹出
     * @param head
     */
    public static void posOrderTwoStacks(TreeNode head) {
        if(head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> collect = new Stack<>();
        stack.push(head);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            collect.push(node);
            if(node.left != null) {
                 stack.push(node.left);
            }
            if(node.right != null) {
                stack.push(node.right);
            }
        }
        while(!collect.isEmpty()) {
            System.out.print(collect.pop().val + " ");
        }
        System.out.println();
    }


    /**
     * 单栈实现后序遍历
     * @param head
     */
    public static void posOrderOneStack(TreeNode head) {
        if(head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        TreeNode cur;
        while(!stack.isEmpty()) {
            cur = stack.peek();
            if(cur.left != null && cur.left != head && cur.right != head) {
                stack.push(cur.left);
            }else if(cur.right != null && cur.right != head) {
                stack.push(cur.right);
            } else {
                System.out.print(cur.val + " ");
                head = stack.pop();
            }
        }
        System.out.println();
    }


    public static List<Integer> posOrderOneStack2(TreeNode head) {
        List<Integer> list = new ArrayList<>();
        if(head == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        TreeNode cur;
        while(!stack.isEmpty()) {
            cur = stack.peek();
            if(cur.left != null && cur.left != head && cur.right != head) {
                stack.push(cur.left);
            }else if(cur.right != null && cur.right != head) {
                stack.push(cur.right);
            } else {
                list.add(cur.val);
                head = stack.pop();
            }
        }
        return list;
    }
}
